package com.lw.leetcode.stack.a;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 1475. 商品折扣后的最终价格
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/9 9:24
 */
public class FinalPrices {


    public static void main(String[] args) {
        FinalPrices test = new FinalPrices();

        // [9,0,1,6]
        int[] prices = {10, 1, 1, 6};

        test.finalPrices(prices);
        System.out.println(Arrays.toString(prices));
    }

    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack = new Stack<>();
        for (int i = prices.length - 1; i >= 0; i--) {
            int v = prices[i];
            while (!stack.isEmpty() && v < stack.peek()) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                prices[i] -= stack.peek();
            }
            stack.add(v);
        }
        return prices;
    }

}
